#pragma once

namespace FibonacciHeapDetail
{
	template <typename Key>
	struct Node;
}

template <typename Key>
struct FibonacciHeap
{
	using Node = FibonacciHeapDetail::Node<Key>;
	using PNodePtr = std::shared_ptr<Node*>;
	using NodeList = std::list<Node*>;
	using NodeListIt = typename NodeList::iterator;

	PNodePtr _minNode;
	NodeList _rootList;
	size_t _num = 0;

	FibonacciHeap() {}
	virtual ~FibonacciHeap() {}
	auto find(const Key& k)->Node*;
	auto insert(const Key& k)->PNodePtr;
	auto insert(PNodePtr pNode)->PNodePtr;
	auto erase(const Key& k)->PNodePtr;
	auto erase(Node* pNode)->PNodePtr;
	//auto erase(const Key& k, InnNode* pMergeNode)->std::pair<DataListIt, bool>;
	void merge(FibonacciHeap& other);
	auto extractMin()->PNodePtr;
	void consolidate();
	void link(Node* pNode, Node* pParent);
	void decreaseKey(Node* pNode, const Key& k, bool del = false);
	void cut(Node* pNode1, Node* pNode2);
	void cascadingCut(Node* pNode);

	template <typename Func>
	auto show(std::ostream& os, Func func) const->std::ostream&;
	bool verify();
};

#include "FibonacciHeapImpl.h"